package 矩阵中的路劲;

//https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/submissions/
public class Solution {
    public boolean exist(char[][] board, String word) {
        char[] str = word.toCharArray();
        char firstChar = str[0];

        int jLength = board.length;
        int iLength = board[0].length;
        char[][] clone = new char[jLength][iLength];

        for (int i1 = 0; i1 < clone.length; i1++) {
            char[] boardChild1 = clone[i1];
            for (int i2 = 0; i2 < boardChild1.length; i2++) {
                clone[i1][i2] = '0';
            }
        }

        for (int j = 0; j < board.length; j++) {
            char[] boardChild = board[j];
            for (int i = 0; i < boardChild.length; i++) {
                if(board[j][i] == firstChar){
                    if(find(i,iLength,j,jLength,board,clone,1,str)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean find(int i,int iLengh,int j,int jLength,char[][] board,char[][] temp,int index,char[] str){

        if(index == str.length){
            return true;
        }

        temp[j][i] = 1;
        boolean state = false;
        if(!state && j -1 > -1 && temp[j-1][i] == '0' && (board[j-1][i] == str[index]) ){
            state = find(i,iLengh,j-1,jLength,board,temp,index+1,str);
        }
        if(!state && j + 1 < jLength  && temp[j+1][i] == '0' && (board[j+1][i] == str[index]) ){
            state = find(i,iLengh,j+1,jLength,board,temp,index+1,str);
        }
        if(!state && i -1 > -1 && temp[j][i-1] == '0' && (board[j][i-1] == str[index]) ){
            state = find(i-1,iLengh,j,jLength,board,temp,index+1,str);
        }
        if(!state && i+1 < iLengh && temp[j][i+1] == '0' && (board[j][i+1] == str[index]) ){
            state = find(i+1,iLengh,j,jLength,board,temp,index+1,str);
        }

        temp[j][i] = '0';

        return state;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
//        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
//        String word = "ABCCED";
//        char[][] board = new char[][]{{'A','B'},{'C','D'}};
//        String word = "ABCD";
//        char[][] board = new char[][]{{'A','A'}};
//        String word = "AAA"; 
        
//        char[][] board = new char[][]{{'C','A','A'},{'A','A','A'},{'B','C','D'}};  [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
//"ABCESEEEFS"
//        String word = "AAB";
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        String word = "ABCESEEEFS";
//        System.out.println(board[0][7]);
        System.out.println(s.exist(board,word));
    }
}
